class Solution:
    def stoneGameVII(self, stones: list) -> int:
        def func(stones, start, end, sumVal, cache):
            if start >= end:
                return 0
            if (start, end) in cache:
                return cache[(start, end)]
            res = max(
                sumVal - stones[start] -
                func(stones, start + 1, end, sumVal - stones[start], cache),
                sumVal - stones[end] -
                func(stones, start, end - 1, sumVal - stones[end], cache))
            cache[(start, end)] = res

            return res

        sumVal = 0
        for stone in stones:
            sumVal += stone
        return func(stones, 0, len(stones) - 1, sumVal, {})
